The present disclosure generally relates to a radix tree, and more particularly to maintaining a compressed radix tree.
A radix tree is a data structure that is used to store data. A radix tree may be useful for constructing associative arrays with keys that can be expressed as strings. In a conventional radix tree, the string at each node is compared chunk by chunk, where the quantity of bits in that chunk at that node is the radix r of the radix tree. A radix tree typically supports insertion, deletion, and search operations. The insertion operation adds a new string to the radix tree while trying to minimize the amount of data stored. The deletion operation removes a string from the radix tree. A search operation may include an exact lookup of a string, a lookup of a predecessor or successor of the string, or a lookup of all strings with a particular prefix. To determine whether a radix tree stores a particular key, performing a search operation on the radix tree may take a long time. It may be desirable to store keys in a radix tree such that the lookup time may be reduced.